# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def rob(self, root: TreeNode) -> int:
        if not root:
            return 0
        return max(self.search(root))

    def search(self, root: TreeNode):
        left = self.search(root.left) if root.left else [0, 0]
        right = self.search(root.right) if root.right else [0, 0]
        return [max(root.val + left[1] + right[1], left[0] + right[0]), left[0] + right[0]]


a = Solution()
